#include <iostream>
#include<vector>
#include "Sorting.h"
#include <cstdlib>
#include <algorithm>
#include <random>
#include <time.h>
using namespace std;

int main() {

    ///初始条件设定
    int n = 20000000; //取值个数
    int pairall = n*(n-1)/2;//序偶总数
    double bound = 0.99; //可更改：序偶中逆序数的比例
    double pairbound = pairall*bound; //需要满足的逆序数个数
    int i;

    ///创建四个后面会用到的vectors
    vector<int> asd{},ran{},rev{},mer{}; ///正序、乱序、逆序，合并起来

    for(int i=0;i<n;i++)
    {
        asd.push_back(i);
        ran.push_back(i);
    }

    std::random_device rd;
    std::mt19937 g(rd());
    shuffle(ran.begin(), ran.end(), g);///一个函数，输出为打乱的序列

    ///从打乱的序列中提取一个数，每提取一次，放到rev里面，计算总数，判断是否符合比例
    ///一个先由大到小，再小到大的数组且不存在重复项的数组逆序数个数应该为前方递减数之和，减去从1到个数的累加
    int sum=0,count=0;
    for(i = 0; sum <= pairbound; i++){
        rev.push_back(ran[i]);
        sum += ran[i] - i;
        count++;
    }

    ///让rev从大到小
    sort(begin(rev),end(rev));
    reverse(begin(rev),end(rev));

    ///给asd去重
    for(i=0; i<count; i++){
        asd.erase(asd.begin()+rev[i]-1);
    }

    ///生成mer，前面是rev,后面是asd
    for(i=0; i<count; i++){
        mer.push_back(rev[i]);
    }
    for(i=0; i<n-count; i++){
        mer.push_back(asd[i]);
    }

    ///统计运行时间
    clock_t start,finish;
    double Times1,Times2;
    vector<int> mer1 = mer;
    vector<int> mer2 = mer;

    start=clock();
    ///这里填入需要统计时间的内容
    heapsort(mer1);
    ///
    finish=clock();
    Times1=(double)(finish-start)/CLOCKS_PER_SEC;
    cout<<"start(时钟打点): "<<start<<endl;
    cout<<"finish(时钟打点): "<<finish<<endl;
    cout<<"运行时间(CLK_TCK): "<<Times1<<endl;


    start=clock();
    ///这里填入需要统计时间的内容
    quicksort(mer2);
    ///
    finish=clock();
    Times2=(double)(finish-start)/CLOCKS_PER_SEC;
    cout<<"start(时钟打点): "<<start<<endl;
    cout<<"finish(时钟打点): "<<finish<<endl;
    cout<<"运行时间(CLK_TCK): "<<Times2<<endl;
}



